#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

/**
 * @方法: 动态规划
 * @时间复杂度: o()
 * @空间复杂度: o()
 * @评价:
 */
int dp[10005];
int jump(vector<int>& nums) {
    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < nums.size(); i++) {
        for (int step = 0; step <= nums[i]; step++) {
            if (i + step < nums.size())
                dp[i + step] = min(dp[i + step], dp[i] + 1);
        }
    }
    return dp[nums.size() - 1];
}